#pragma once
#include<iostream>
#include<vector>
using namespace std;

enum Status
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};



template<class K, class V>
class HashTable
{
private:
	vector<HashData<K, V>> _table;
	size_t _sz;//有效数据个数
public:
	HashData<K, V>* Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return nullptr;
		}
		size_t index = key % _table.size();
		while (_table[index]._status != EMPTY)
		{
			if (_table[index]._kv.first == key && _table[index]._status == EXIST)
			{
				return &_table[index];
			}
			index++;
			index %= _table.size();
		}
		return nullptr;
	}
	
	bool Insert(pair<K, V> kv)
	{
		//判断是重复
		bool ret = Find(kv.first);
		if (ret)
		{
			//有重复
			return false;
		}

		//判断是否需要扩容
		if (_table.size() == 0 || _sz * 10 / _table.size() >= 7)
		{
			//扩容
			size_t NewSize = _table.size() == 0 ? 10 : _table.size() * 2;
			//建立新表
			HashTable<K, V> newHT;
			newHT._table.resize(NewSize);

			//遍历原表，把原表中的数据按NewSize映射到新表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._status == EXIST)
				{
					newHT.Insert(_table[i]._kv);
				}
			}
			_table.swap(newHT._table);
		}
		//找插入的位置
		
		//线性探测
		size_t index = kv.first % _table.size();
		while (_table[index]._status == EXIST)
		{
			index++;
			index %= _table.size();
		}
		//找到位置
		_table[index]._kv = kv;
		_table[index]._status = EXIST;
		_sz++;

		return false;
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_status = DELETE;
			_sz--;
			return true;
		}
		return false;
	}
};

void test1()
{
	HashTable<int, int> ht;
	int a[] = { 2, 12, 22, 32, 42, 52, 62 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}
}